from lib import *

class FastMap:
  def __init__(o,t,enough=5): 
    o.table=t
    o.l=[]; o.r=[]
    o.enough=enough
    o.resetCounts()
    o.split()

  def resetCounts(o):
    o.aliens=[]
    o.locals=0
    o.maxA=0
    o.maxB=0
    o.weirdest=None

  def __repr__(o):
    return '# '+str(len(o.l) + len(o.r))+ '{%.2f}' % (100*o.misfits())

  def misfits(o):
    return len(o.aliens)/(o.locals + 0.0001)

  def furthest2(o) :
    if o.weirdest:
      print "going weird"
      anywhere = o.weirdest
    else:
      anywhere  = any(o.table.data) 
    o.west    = o.table.furthest(anywhere)
    o.east    = o.table.furthest(o.west)

  def project(o,row) :
    o.locals += 1
    a = row - o.west
    b = row - o.east
    if a > o.maxA: 
      print "newly weird"
      o.maxA,o.weirdest = a,row
    if b > o.maxA: 
      print "newly weird"
      o.maxB,o.weirdest = b,row
    if a >= o.c: 
      #print a/o.c
      o.aliens.append(row) ; return o.c
    if b >= o.c:
      #print b/o.c
      o.aliens.append(row); return 0
    return (a**2 + o.c**2 - b**2) / (2*o.c)

  def projections(o) :
    o.furthest2()
    o.c = o.west - o.east
    return [(o.project(row),row) for row in o.table.data]

  def leftp(o,lst) :
    return  o.project(lst) < o.max4west

  def split(o): 
    p = sorted(o.projections(),key=first)
    #i = cut(map(first,p) ,sort=False,enough=o.enough,cohen=0)
    i = int(len(p)/2)
    while i < (len(p)-1) and first(p[i]) == first(p[i+1]): i += 1
    o.max4west = first(p[i])
    o.l        = map(lambda x: x[1].data, p[:i])
    o.r        = map(lambda x: x[1].data, p[i:]) 
    return o
